package pro.softzhang.algo.lc800;

import java.util.Arrays;

public class LC886_PossibleBipartition {
    public static void main(String[] args) {

    }

    /**
     * 染色法
     */
    static class Solution {
        int N = 2010, M = 2 * 10010;
        int[] he = new int[N];
        int[] e = new int[M];
        int[] ne = new int[M];
        int[] color = new int[N];
        int idx;

        private void add(int a, int b) {
            e[idx] = b;
            ne[idx] = he[a];
            he[a] = idx++;
        }

        private boolean dfs(int u, int current) {
            color[u] = current;
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (color[j] == current)
                    return false;
                if (color[j] == 0 && !dfs(j, 3 - current))
                    return false;
            }
            return true;
        }

        /**
         * 抄自三叶
         * @param n
         * @param dislikes
         * @return
         */
        public boolean possibleBipartition(int n, int[][] dislikes) {
            Arrays.fill(he, -1);
            for (int[] info : dislikes) {
                int a = info[0], b = info[1];
                add(a, b);
                add(b, a);
            }

            for (int i = 1; i <= n; i++) {
                if (color[i] != 0)
                    continue;
                if (!dfs(i, 1))
                    return false;
            }
            return true;
        }
    }

    /**
     *
     */
    static class Solution1 {
        public boolean possibleBipartition(int n, int[][] dislikes) {
            return false;
        }
    }
}
